1. Field of Invention
The present invention relates to PCB automatic routing technology. More particularly, the present invention relates to a routing storage structure based on directional grid points and a routing method thereof.
2. Description of Related Art
PLCs (Programmable Logic Controllers) have been widely applied in the industrial automation field in recent times. The user writes a logic control program using PLC programming software, compiles the software and then loads the software to the PLC, thereby realizing customized control requirements of the user. Generally, the PLC development environment provides many programming languages, such as IL (Instruction List), ST (Structured Text), LD (Ladder Diagram), FBD (Function Block Diagram), SFC (Sequential Function Chart) and CFC (Continuous Function Chart).
The CFC programming language has been widely accepted because of its characteristics of flexibility, intuitiveness and simplicity. With a CFC programming language module, when the user creates a program window, i.e., a routing plane, the user can add, delete, and move function blocks to operate the blocks of the automatic routing system. When the user performs the operation of connection from one instruction pin to another instruction pin, the connecting path between the two points has been performed by the automatic routing module. In the prior art, the routing algorithm typically employs a maze algorithm, a line-exploring method or an improved algorithm based on the two algorithms, but the routing storage structure of all these algorithms needs storing a block set. That is, the routed route and the block are respectively stored in the line linked list and the block linked list by means of a linked list storage. All the routed lines are recorded in the line linked list, and each line is indicated by a point linked list composed of the inflection points of the line. The position and size information of all the blocks in the routing plane are recorded in the block linked list.
However, according to the storage structure of the routing system in the prior art, if it is assumed that it is requested to accomplish the automatic routing from point A to point B, and that the line linked list includes n nodes, each line has m inflection points on average, and the block linked list includes k nodes, in order to accomplish the automatic routing from point A to point B by the routing algorithm, it is necessary to determine whether L grid points belong to the block set. That is, the maximum traversal times N of the linked list nodes are represented as L×k×n×m, so that the traversal times N are in positive correlation with the complexity of the block set (i.e., the node quantity of the block linked list), and further the routing speed is in negative correlation with the complexity of the block set. Furthermore, with the increase of the complexity of the block set, the storage space occupied by the storage structure increases rapidly, thereby resulting in an abrupt drop in the routing efficiency.
In view of the above, many in the industry are endeavoring to design a more efficient routing storage structure, so as to reduce or eliminate the impact of the complexity of the block set on the automatic routing algorithm and to reduce by as much as possible the storage space occupied by the storage structure, thereby improving the routing efficiency.